Cellular Automata and the Game of Go

Two-dimensional cellular automata can be used to evaluate final board positions in the game of Go. The rules of the game can be found online. The board is represented as an array of characters, with 'b' for black pieces, 'w' for white pieces, and '.' for empty points:

bbbbbbbbb
bbbbbbbbb
bbbwwwbbb
bbbw.wbbb
bbbwwwbbb
bbbw.wbbb
bbbwwwbbb
bbbbbbbbb
bbbbbbbbb

First dead pieces are removed (captured), then the board is scored:

board after removals:
.........
.........
...www...
...w.w...
...www...
...w.w...
...www...
.........
.........
blackRemovedCount = 66 whiteRemovedCount 0
score (black - white) not including removals = -68

During dead piece removal the cellular automata update converts 'b' (black piece) or 'w' (white piece) to 'B' or 'W' if it is adjacent to a '.' (empty point) or another 'B' or 'W'. After 2*(boardSize-1) steps the cellular automata will have propagated the information about connectivity to empty points across the entire board. Pieces which have not been capitalized are removed.

During scoring the cellular automata marks empty points adjacent to pieces or claimed points with 'B' or 'W' to indicate ownership. If both sides claim the point it is marked as 'X' and neither side counts it. After 2*(boardSize-1) steps the cellular automata will have propagated the information about ownership across the entire board.

Ruby code implementing these cellular automata is available here. This code includes optional C code called by Ruby which accelerates board scoring by 200x.

Brute Force Go

It is not realistic to use simple min-max search on Go. With a 19x19 board the first turns provide about 19x19 alternative moves, versus about 35 alternative moves for Chess. And static board evaluation is much more difficult. The resistance of the game of Go to brute-force analysis has led AI researchers to propose it serve as the new "drosophila" of AI after Chess. Nevertheless, cellular automata could be incorporated into a heuristics or pattern-based game AI engine.

Conway, Life, and Go

Combinatorial game theory can be used to analyze Go board positions. John Conway is a pioneer in this field of mathematics. He is also the inventor of the most famous cellular automata, the two-dimensional game of life. He also invented surreal numbers to analyze Go endgames.